import entity.TreeNode;

import java.util.HashMap;

public class ConstructBTreeFromInAndPostOrder {
    /*
    * 106. 从中序与后序遍历序列构造二叉树
    * 给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历，
    * postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
    *
    * 1 <= inorder.length <= 3000
    * postorder.length == inorder.length
    * -3000 <= inorder[i], postorder[i] <= 3000
    * inorder 和 postorder 都由 不同 的值组成
    * postorder 中每一个值都在 inorder 中
    * inorder 保证是树的中序遍历
    * postorder 保证是树的后序遍历
    * */
    public static void main(String[] args){
        ConstructBTreeFromInAndPostOrder o = new ConstructBTreeFromInAndPostOrder();
        o.solution(new int[]{9,3,15,20,7}, new int[]{9,15,7,20,3});
    }

    // 我的想法：构造树，自然是从底开始构造
    // 利用两个遍历方式，确定顶和左右儿子
    // 相同索引处相等，说明是左儿子
    // 不等，中序是顶，后序是右儿子的最深层左叶子
    // 不对，脑袋瓜不是很聪明，直接模拟想不出来
    public TreeNode mySolution(int[] inorder, int[] postorder){
        TreeNode res = null;
        for (int i = 0; i < inorder.length; i++) {

        }
        return res;
    }

    // 首先，你得知道中序和后续遍历顺序的联系，不知道的话干想是想不出来的！！！
    // 要有理论指导实践！！！
    // 还是递归
    // 来看一下一共分几步：
    //
    //  第一步：如果数组大小为零的话，说明是空节点了。
    //  第二步：如果不为空，那么取后序数组最后一个元素作为节点元素。
    //  第三步：找到后序数组最后一个元素在中序数组的位置，作为切割点
    //  第四步：切割中序数组，切成中序左数组和中序右数组 （顺序别搞反了，一定是先切中序数组）
    //  第五步：切割后序数组，切成后序左数组和后序右数组
    //  第六步：递归处理左区间和右区间

    //可以先用一个map存下索引值，这样就不用每次都遍历了,善用map！！！！！
    HashMap<Integer, Integer> map = new HashMap<>();
    public TreeNode solution(int[] inorder, int[] postorder){
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i], i);
        }
        return build(inorder, 0, inorder.length, postorder, 0, postorder.length);
    }
    // 1.当然需要返回节点用于构造树， 传入两个数组，以及截取的索引(左闭右开)
    private TreeNode build(int[] inorder, int inStart, int inEnd,
                           int[] postorder, int postStart, int postEnd){
        // 循环不变量 区间定义不存在则说明到底了, 两个数组的长度一定是相等的，只需判断post的就行
        if(postStart >= postEnd)
            return null;
        // 找出post数组中的最后一个节点，这个节点是当前子树的根
        TreeNode root = new TreeNode(postorder[postEnd-1]);
        // 叶子节点，直接返回
        if(postEnd - postStart == 1)
            return root;
        // 开始裁剪数组
        // 首先找到inorder中和当前根相等的节点，该节点左边的数组就是左子树，右边的数组就是右子树
        int index = map.get(root.val);
        int cut = postStart+(index-inStart);
        root.left = build(inorder, inStart, index, postorder, postStart, cut);
        root.right = build(inorder, index+1, inEnd, postorder, cut, postEnd-1);
        return root;
    }
}
